//
//  BinaryTree_18.swift
//  ArithmeticClass15
//
//  Created by xiangzuhua on 2020/12/2.
//

import UIKit

class BinaryTree_18: NSObject {

    // 前序遍历
    class func traversal(frontWithNode node: BinaryListNode?) {
        if node == nil {
            return
        }
        print(node!.value)
        traversal(frontWithNode: node?.left)
        traversal(frontWithNode: node?.right)
        
    }
    
    // 中序遍历
    class func traversal(middleWithNode node: BinaryListNode?){
        if node == nil {
            return
        }
        traversal(middleWithNode: node?.left)
        print(node!.value)
        traversal(middleWithNode: node?.right)
    }
    
    // 后序遍历
    class func traversal(behindWithNode node:BinaryListNode?){
        if node == nil {
            return
        }
        traversal(behindWithNode: node?.left)
        traversal(behindWithNode: node?.right)
        print(node!.value)
    }
    
}
    
// MARK:-二叉查找树
class BinaryFindTree: NSObject {
    /// 查询
    class func find(treeNode: BinaryListNode?, findValue value: Int) -> BinaryListNode?{
        
        var head = treeNode
        
        while head != nil {
            if head?.value == value {
                return head
            }
            if head!.value > value {
                head = head?.left
            } else {
                head = head?.right
            }
        }
        return nil
    }
    /// 插入
    class func insert(tree: BinaryListNode?, insertNode node: BinaryListNode?) -> Bool{
        if node == nil {
            return false
        }
    
        var head = tree
        while head != nil {
            if head!.value < node!.value {
                if head?.right == nil {
                    head?.right = node
                    return true
                } else {
                    head = head?.right
                }
            } else if(head!.value > node!.value){
                if head?.left == nil {
                    head?.left = node
                    return true
                } else {
                    head = head?.left
                }
            }
        }
        return false
    }
    
    /// 从二叉查找树中删除指定的节点
    /// - Parameters:
    ///   - tree: 要进行节点删除的查找树
    ///   - value: 节点的值
    /// - Returns: 是否删除成功
    class func delet(_ tree: BinaryListNode?, deletValue value: Int){
        //分为三种情况，一种是要删除的节点没有子节点，第二种是要删除的节点只有一个子节点，第三种是要删除的节点有两个子节点
        // 查找节点
        var head = tree
        var fatherHead: BinaryListNode?
        while head != nil && head?.value != value{
            fatherHead = head
            if head!.value > value {
                head = head?.left
            } else {
                head = head?.right
            }
        }
        // 没有找到
        if head == nil {
            return
        }
        
        // 左右子节点都有值，找到要删除的节点右分支的最小值节点
        if head?.left != nil && head?.right != nil {
            var minNode = head?.left // 最小值的节点
            var minFatherNode = head // 最小值节点的父节点
            while minNode?.left != nil {
                minFatherNode = minNode
                minNode = minNode?.left
            }
            
            // 删除的节点替换为最小节点
            head?.value = minNode!.value
            // 变成删除最小节点
            head = minNode
            fatherHead = minFatherNode
        }
        
        // 只有左子节点或者右子节点，或者没有子节点
        var childNode: BinaryListNode?
        if head?.left != nil {
            childNode = head?.left
        } else if head?.right != nil {
            childNode = head?.right
        } else {
            childNode = nil
        }
        
        if fatherHead == nil { // 删除的是根节点
            head = childNode
        } else if fatherHead?.left == head {
            fatherHead?.left = childNode
        } else if fatherHead?.right == head {
            fatherHead?.right = childNode
        }
    }
    
    // 求二叉查找树的高度（根节点的高度，即根节点到叶子节点的边数）
    class func getHeight(tree:BinaryListNode?) -> Int {
        if tree?.left == nil && tree?.right == nil {
            return 1
        } else if(tree?.left == nil && tree?.right != nil){
            return getHeight(tree: tree?.right) + 1
        } else if(tree?.right == nil && tree?.left != nil){
            return getHeight(tree: tree?.left) + 1
        } else {
            return max(getHeight(tree: tree?.left), getHeight(tree: tree?.right)) + 1
        }
    }
}
